#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        int len = words[0].size();
        unordered_map<string, int> hash1;
        vector<int> res;

        int left = 0;
        int right = 0;
        for (int i = 0; i < words.size(); i++)
        {
            hash1[words[i]]++;
        }

        int count = 0;
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash2;
            for (left = i, right = i; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash2[in] <= hash1[in])count++;

                if (right - left + 1 > len * words.size())
                {
                    string out = s.substr(left, len);
                    if (hash2[out] <= hash1[out])count--;
                    hash2[out]--;
                    left += len;
                }

                if (count == words.size())res.push_back(left);
            }
            count = 0;
        }

        return res;
    }
};

int main()
{
    Solution s1;
    vector<string> v1;
    v1.push_back("foo");
    v1.push_back("bar");

    string s("wordgoodgoodgoodbestword");

    s1.findSubstring(s, v1);
	return 0;
}